package 组合问题;

import java.util.*;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 组合总和II,与组合问题一,不同的点在于便利的的起始位置,以及去重裁剪
 * @date 2022/11/13 17:40
 */
public class Demo40 {
    public static void main(String[] args) {
        int[] candidates={10,1,2,7,6,1,5};
        int target=8;
        res = combinationSum2(candidates, target);
        System.out.println(res);

    }
    static List<List<Integer>> res=new ArrayList<>();
    static LinkedList<Integer> path=new LinkedList<>();
    static int sum=0;
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTrack(candidates,0,target);
        return res;
    }
    private static void backTrack(int[] candidates, int startIndex, int target) {
        if(sum>target){
            return;
        }
        if(sum==target){
            ArrayList<Integer> temp=new ArrayList<>(path);
            res.add(temp);
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            if(i>startIndex&&candidates[i]==candidates[i-1]){
                    continue;
            }
            path.add(candidates[i]);
            sum=sum+candidates[i];
            backTrack(candidates, i+1, target);
            path.removeLast();
            sum=sum-candidates[i];
        }
    }

}
